package LeetCode刷题;

import java.util.LinkedList;
import java.util.Stack;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-11-15 15:51
 * @description: Functions of this class is
 * 官方题解：
 * 较好，空间复杂度：O（1）
 * 我们可以先将给定的链表连接成环，然后将指定位置断开
 * class Solution {
 *    public ListNode rotateRight(ListNode head, int k) {
 *        if(head!=null&&k>0){
 *            int len=1;
 *            ListNode tail=head;
 *            while(tail.next!=null){
 *                ++len;//算出链表长度
 *                tail=tail.next;
 *            }
 *            int index=len-(k%len);//算出链表连成环的时候，断开的位置
 *            if(index==len){//如果断开的就为头节点，则直接返回原来的链表
 *                return head;
 *            }
 *            tail.next=head;//头尾相连，形成环
 *
 *            while(index-->0){//然后开始定位到要断开的位置
 *                tail=tail.next;
 *            }
 *            ListNode disc=tail.next;//找到断开的位置
 *            tail.next=null;
 *            return disc;
 *        }
 *        return head;
 *     }
 * }
 **/
public class No旋转链表 {
    public static void main(String args[]){

    }
    /**
     * 自我做法：空间复杂度O（n）
     * public ListNode rotateRight(ListNode head, int k) {
     *         if(head!=null&&k!=0){
     *             ListNode h=head;
     *             LinkedList<Integer> queue=new LinkedList<Integer>();
     *             while(h!=null){
     *                 queue.add(h.val);
     *                 h=h.next;
     *             }
     *             k=(k>queue.size())?(k%queue.size()):k;//如果k超过链表的长度，则%他的长度
     *             while(k-->0){
     *                 int val=queue.pollLast();
     *                 queue.addFirst(val);
     *             }
     *             head=new ListNode();
     *             while(!queue.isEmpty()){
     *                 ListNode p=new ListNode(queue.pollLast());
     *                 p.next=head.next;
     *                 head.next=p;
     *             }
     *             return head.next;
     *         }
     *         return head;
     *     }
     */

}